/**
 * 
 */
package dp.passed;

import java.util.ArrayList;
import java.util.List;

import utils.PrintUtils;

/**
 * @author xyyi
 * 
 */
public class JumpGame {

    /**
     * Given an array of non-negative integers, you are initially positioned at
     * the first index of the array.
     * 
     * Each element in the array represents your maximum jump length at that
     * position.
     * 
     * Determine if you are able to reach the last index.
     * 
     * For example: A = [2,3,1,1,4], return true.
     * 
     * A = [3,2,1,0,4], return false.
     */
    public boolean canJump(int[] A) {
        int maxCover = 0;
        for (int start = 0; start <= maxCover && start < A.length; start++) {
            maxCover = Math.max(maxCover, A[start] + start);
            if (maxCover >= A.length - 1)
                return true;
        }
        return false;
    }

    boolean canJumpA(int A[]) {
        int[] jump = new int[A.length];
        jump[0] = 0;
        for (int i = 1; i < A.length; i++) {
            jump[i] = Math.max(jump[i - 1], A[i - 1]) - 1;
            if (jump[i] < 0)
                return false;
        }
        return jump[A.length - 1] >= 0;
    }

    /**
     * Jump Game II
     * 
     * Given an array of non-negative integers, you are initially positioned at
     * the first index of the array.
     * 
     * Each element in the array represents your maximum jump length at that
     * position.
     * 
     * Your goal is to reach the last index in the minimum number of jumps.
     * 
     * For example: Given array A = [2,3,1,1,4]
     * 
     * The minimum number of jumps to reach the last index is 2. (Jump 1 step
     * from index 0 to 1, then 3 steps to the last index.)
     */
    public int jump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (A.length <= 1)
            return 0;

        int start = 0;
        int end = 0;
        int counter = 0;
        while (end < A.length) {
            int max = 0;
            counter++;
            for (int i = start; i <= end; i++) {
                int currJump = A[i] + i;
                if (currJump >= A.length - 1) {
                    return counter;
                }
                max = Math.max(max, currJump);
            }
            start = end + 1;
            end = max;
        }

        return counter;
    }

    public JumpGame() {
        // TODO Auto-generated constructor stub
    }

    int jumpDP(int A[]) {
        int steps = 0, n = A.length, f[] = new int[1000];
        if (n == 1)
            return 0;
        for (int i = 0; i < n; i++) {
            if (f[steps] < i)
                steps++;
            f[steps + 1] = Math.max(f[steps + 1], i + A[i]);
            if (f[steps + 1] >= n - 1)
                return steps + 1;
        }
        return steps;
    }

    int jumpDP2(int A[]) {
        if (A.length <= 1)
            return 0;

        int steps = 0, currMaxCover = 0, nextMaxCover = 0;
        for (int i = 0; i < A.length; i++) {
            if (currMaxCover < i) {
                steps++;
                currMaxCover = nextMaxCover;
                nextMaxCover = 0;
            }
            nextMaxCover = Math.max(nextMaxCover, i + A[i]);
            if (nextMaxCover >= A.length - 1)
                return steps + 1;
        }

        return steps;
    }

    public List<Integer> jumpDP2List(int A[]) {
        List<Integer> result = new ArrayList<Integer>();
        if (A == null || A.length == 0)
            return result;

        if (A.length == 1) {
            result.add(A[0]);
            return result;
        }

        int currMaxCover = 0, nextMaxCover = 0;
        int nextMaxCoverStart = 0;
        for (int i = 0; i < A.length; i++) {
            if (currMaxCover < i) {
                result.add(A[nextMaxCoverStart]);
                currMaxCover = nextMaxCover;
                nextMaxCover = 0;
            }
            if (i + A[i] > nextMaxCover) {
                nextMaxCover = i + A[i];
                nextMaxCoverStart = i;
            }

            if (nextMaxCover >= A.length - 1) {
                result.add(A[nextMaxCoverStart]);
                result.add(A[A.length - 1]);
                return result;
            }
        }

        return result;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        JumpGame jg = new JumpGame();
        int[] A = { 0, 2, 2 };
        System.out.println(jg.jumpDP2(A));

        List<Integer> path = jg.jumpDP2List(A);
        PrintUtils.printList(path);
    }
}
